|
|
Longest Prefix Match Algorithms
Sedlář, František ; Puš, Viktor (referee) ; Tobola, Jiří (advisor)
This bachelor's thesis deals with a description of basic longest prefix match (LPM) algorithms. Another algorithm - LC Trie - was added to existing implementations into the Netbench library. All the algorithms which the library includes were tested with real groups of IPv6 prefixes. They were compared on the basis of previously obtained data. Testing scripts for each of the algorithms were implemented as well as scripts for downloading groups of prefixes from significant sources on the internet.
|
|
|
Longest Prefix Match Algorithms
Sedlář, František ; Matoušek, Jiří (referee) ; Tobola, Jiří (advisor)
This master's thesis explains basics of the longest prefix match (LPM) problem. It analyzes and describes chosen LPM algorithms considering their speed, memory requirements and an ability to implement them in hardware. On the basis of former findings it proposes a new algorithm Generic Hash Tree Bitmap. It is much faster than many other approaches, while its memory requirements are even lower. An implementation of the proposed algorithm has become a part of the Netbench library.
|
|
|
Longest Prefix Match Algorithms
Suchodol, Jaroslav ; Puš, Viktor (referee) ; Tobola, Jiří (advisor)
This work deal with routing in IP networks, particularly the issue of finding the longest matched prefix. Problems of finding the longest matched prefix solves many sophisticated algorithms. The main task of this work focuses on the following algorithms - Controlled Prefix Expansion, Lulea Compressed Tries, Binary search on intervals and Binary search on prefix length. Algorithms are described and followed by software implementation in Python. Output work is the analysis/comparison of different algorithms in terms of memory consumption and number of memory accesses at worst.
|
|
|
Longest Prefix Match Algorithms
Suchodol, Jaroslav ; Puš, Viktor (referee) ; Tobola, Jiří (advisor)
This work deal with routing in IP networks, particularly the issue of finding the longest matched prefix. Problems of finding the longest matched prefix solves many sophisticated algorithms. The main task of this work focuses on the following algorithms - Controlled Prefix Expansion, Lulea Compressed Tries, Binary search on intervals and Binary search on prefix length. Algorithms are described and followed by software implementation in Python. Output work is the analysis/comparison of different algorithms in terms of memory consumption and number of memory accesses at worst.
|
|
|
Longest Prefix Match Algorithms
Sedlář, František ; Puš, Viktor (referee) ; Tobola, Jiří (advisor)
This bachelor's thesis deals with a description of basic longest prefix match (LPM) algorithms. Another algorithm - LC Trie - was added to existing implementations into the Netbench library. All the algorithms which the library includes were tested with real groups of IPv6 prefixes. They were compared on the basis of previously obtained data. Testing scripts for each of the algorithms were implemented as well as scripts for downloading groups of prefixes from significant sources on the internet.
|
|
|
Longest Prefix Match Algorithms
Sedlář, František ; Matoušek, Jiří (referee) ; Tobola, Jiří (advisor)
This master's thesis explains basics of the longest prefix match (LPM) problem. It analyzes and describes chosen LPM algorithms considering their speed, memory requirements and an ability to implement them in hardware. On the basis of former findings it proposes a new algorithm Generic Hash Tree Bitmap. It is much faster than many other approaches, while its memory requirements are even lower. An implementation of the proposed algorithm has become a part of the Netbench library.
|
guest ::
